Problem 594 Longest Harmonious Subsequence
找出最大值和最小值相差不大于1的最长子序列,子序列不要求数组连续.
主要思路:
这个题目一个很直观的思路就是排序之后找出两个相邻不等的值的最长长度,先排序,再使用map存储数据,再循环如果两个数之差不大于1就计数.后来看别人的思路,有人采用map加上单次循环的策略,省略了排序这个步骤.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public int findLHS(int[] nums) {
int max = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
int lower = map.getOrDefault(num - 1, 0);
int upper = map.getOrDefault(num + 1, 0);
if (lower != 0) max = Math.max(max, lower + map.get(num));
if (upper != 0) max = Math.max(max, upper + map.get(num));
}
return max;
}
}
代码说明:
以题目给出的1,3,2,2,5,2,3,7为例,循环开始之后map的情况为{1=1},由于max和min的差距不大于1,也就是说取比当前值大1或者小1或当前值均可,lower=0,upper=0;开始第二轮循环,map的情况为{1=1,3=1},lower=0,upper=0;第三轮循环,map的情况为{1=1,2=1,3=1},lower=1,upper=1,由于lower!=0,max=lower+当前值=2,upper=upper+当前值=2;第四轮循环,map的情况为{1=1,2=2,3=1},lower=lower+当前值=3,upper=3…从这里大致就能理解整个逻辑了,也就是从循环中取值,判断当前值的前后是否有值,如果有则将其前项或后项的值和当前值相加,判断它们与max之间的关系,如果比max大则更新max.
Problem 606 Construct String from Binary Tree
将二叉树的结构输出成String,当左子树为空的时候保留输出(),当右子树为空时不输出(),其余时候均为(node.val)
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public String tree2str(TreeNode t) {
if (t == null) {
return "";
}
String output = String.valueOf(t.val);
if (t.left != null || t.right != null) {
output += "(" + tree2str(t.left) + ")";
if (t.right != null) {
output += "(" + tree2str(t.right) + ")";
}
}
return output;
}
}
代码说明:
该题只需要简单的判断即可遍历完成,唯一需要注意的点就是左子树为空时需要补全(),也就是需要加一层判断
Problem 617 Merge Two Binary Trees
如题目名所说,合并两棵树,若对应结点均有值则相加,没有则由另一个课的值补全.
主要思路:
还是传统方法,先判断各自节点的安全性,之后就是对对应点相加并且同时遍历两棵树的左子树和右子树,不过这里需要注意的是由于两棵树合并之后的树相当于是新树,所以可以重新创建结点.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (t1==null&&t2==null)
return null;
if (t1==null)
return t2;
if (t2==null)
return t1;
TreeNode res = new TreeNode(t1.val+t2.val);
res.left = mergeTrees(t1.left,t2.left);
res.right = mergeTrees(t1.right,t2.right);
return res;
}
}
Problem 643 Maximum Average Subarray I
找出给定个数的和最大的子序列
主要思路:
这个题目其实用双循环可以简单解决,但是双循环很容易触发时间限制.所以可以采用滑动窗口策略,所谓滑动窗口就是先将指定数量(比如K)的数组元素相加,之后以K为起始点,减去i-K
位置的元素,加上当前位置的元素即可完成一次滑动.比如题目中给出的K=4,先算出0 1 2 3元素的和,再从4开始计算,先用和减去0位置的元素,再加上4位置的元素,并且比较和与最大值的大小,之后依次循环.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for(int i = 0;i<k;i++)
sum+= nums[i];
int res = sum;
for(int i = k;i<nums.length;i++){
sum += nums[i]-nums[i-k];
res = Math.max(res,sum);
}
return (double) res/k;
}
}
Problem 653 Two Sum IV - Input is a BST
找出二叉搜索树中是否存在两个数相加等于给定值.
主要思路:
既然是二叉搜索树,那么使用中序遍历自然能获得一个排序好的序列,之后只要存入map,判断给定值-当前值在map中是否存在即可.但是这样的效率似乎不够高.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> tree = new ArrayList<>();
boolean flag = false;
public boolean findTarget(TreeNode root, int k) {
treeIn(root);
Map<Integer,Boolean> map = new HashMap<>();
if (tree.size()<2)
return false;
else {
if (k<(tree.get(0)+tree.get(1))||k>(tree.get(tree.size()-1)+tree.get(tree.size()-2)))
return false;
for (int i=0;i<tree.size();i++){
map.put(tree.get(i),true);
}
for (int i=0;i<tree.size();i++){
map.put(tree.get(i),false);
flag = map.get(k-tree.get(i))==null?false:map.get(k-tree.get(i));
if (flag)
return true;
}
return flag;
}
}
public List<Integer> treeIn(TreeNode root){
if (root==null)
return tree;
else {
treeIn(root.left);
tree.add(root.val);
treeIn(root.right);
}
return tree;
}
}
Problem 665 Non-decreasing Array
在至多可以替换一个数字的条件下,判断当前整数数组是否满足单调不减.
主要思路:
该题主要是判断两种情况:
- 出现两次当前数比其后一位数字要大
- 只出现一次当前数比其后一位数字大,但是其后两位数字却比其前一位数字要小,比如5,6,7,10,3,4,5.这里只有10>3属于当前数大于后一位数的情况,但是10之后的3,4,5都不大于10之前的数,所以就算更改10,也无法改变当前数组不属于单调不减数组的情况.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public boolean checkPossibility(int[] nums) {
for(int i = 0; i < nums.length - 1; i++){
if(nums[i] > nums[i+1]){
for(int j = i + 1; j < nums.length - 1; j++){
if (nums[j] > nums[j+1])
return false;
}
if(i == 0 || i + 2 > nums.length - 1){
return true;
}
if(nums[i] > nums[i + 2]){
return nums[i - 1] <= nums[i + 1];
}
return true;
}
}
return true;
}
}
Problem 669 Trim a Binary Search Tree
给点最小值和最大值,将二叉搜索树中不在此范围内的结点进行裁剪,重新组成一颗二叉搜索树.
主要思路:
以根结点为出发点构建树,如果最小值比root大则进入右子树并将其作为新的root,如果最大值比root小,则进入左子树,并将其作为新的root,之后只需要常规的递归就能得到裁剪后的二叉搜索树.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root==null)
return null;
if (L>root.val){
root = trimBST(root.right,L,R);
}else if (R<root.val){
root = trimBST(root.left,L,R);
}
else{
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
}
return root;
}
}
Problem 680 Valid Palindrome II
在至多删除一个字符的情况下,判断字符串是否属于回文.
主要思路:
这个题目开始思考的时候还在想如果遇到需要删除的情况如何处理,但其实这题的关键就是抓住回文序列对应相等即可,如果遇到不相等的情况则删除左边字符或者右边字符.最后综合判断两边的情况.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public boolean validPalindrome(String s) {
return helper(s, 0, s.length() - 1, true);
}
private boolean helper(String s, int l, int r, boolean okRemove) {
if (l >= r)
return true;
if (s.charAt(l) == s.charAt(r))
return helper(s, l + 1, r - 1, okRemove);
else
return okRemove && (helper(s, l + 1, r, false) || helper(s, l, r - 1, false));
}
}
Problem 696 Count Binary Substrings
寻找字符串中0和1数量相同的子序列的个数
主要思路:
本题也属于数数问题,这类计数比较问题都可以通过暴力循环解决,但是时间复杂度上无法通过.就这题来说处理的关键在于从0变到1和1变到0的过程.以001110011为例.它可以划分成0011、1100、0011这三大部分,而这些部分是这样选取的,先统计00为2个,然后遍历到111,此时虽然有3个1,但是根据题目要求0和1数量要相同,所以只能取2个1.然后这3个1切换到0时,0也有2个,此时依然只能取2个1,也就是说部分的选取是以0和1切换之后0和1的数量中较小的那个决定的.而在类似(00001111)内部自然可以组成(01)对组合(此处为4对),把握好这个关系就能求解出来.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public int countBinarySubstrings(String s) {
if(s == null || s.length() == 0) return 0;
int rem = 0, count = 1;
int result = 0;
for(int i = 1; i < s.length(); i++) {
if(s.charAt(i) == s.charAt(i - 1))
count ++;
else {
rem = count;
count = 1;
}
if(count <= rem)
result ++;
}
return result;
}
}
代码说明:
这里的rem就是用来保留切换前的0或者1的数量,然后当新的1或0的数量赶上rem的值之前result++.
Problem 687 Longest Univalue Path
寻找值相同的最长路径.
主要思路:
采用后项遍历对二叉树进行遍历,原因是计算左右子树相同,其父结点与它们不同则无法形成通路.而在递归的过程中需要注意几个问题.其中最重要的就是值的返回问题,这里返回的是
Math.max(rootWithLeft, rootWithRight),它是指的单个结点的左右子树中相同值的最大深度,因为左右子树路径必然只能选择其一.当遍历完一个完成左右子树+父结点后就开始比较该路径与最大路径的大小.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int longestUnivaluePath(TreeNode root) {
int[] res = {0};
helper(root, res);
return res[0];
}
private int helper(TreeNode node, int[] res) {
if (node == null) return 0;
int left = helper(node.left, res);
int right = helper(node.right, res);
int rootWithLeft = 0, rootWithRight = 0;
if (node.left != null && node.left.val == node.val) {
rootWithLeft = 1 + left;
}
if (node.right != null && node.right.val == node.val) {
rootWithRight = 1 + right;
}
res[0] = Math.max(res[0], rootWithLeft + rootWithRight);
return Math.max(rootWithLeft, rootWithRight);
}
}